10242. Knight route
Given a n * n board
with the Knight placed in the first row and first column of an empty board.
Moving according to the rules of chess knight, visit each square exactly once.
Print the order of each the
cell in which they are visited.
Input.
The size of the chess board n (1 ≤ n ≤ 8).
Output. Print the state of the board with knight moves. If the problem has no
solution, print “Solution does not exist”.
|
Sample input 1 |
Sample output 1 |
|
5 |
1 6 15 10 21 14 9 20 5 16 19 2 7 22 11 8 13 24 17 4 25 18 3 12 23 |
|
|
|
|
Sample input 2 |
Sample output 2 |
|
2 |
Solution does not exist |
backtracking
The knight’s moves are numbered from 1 to n2. Declare a two dimensional array sol, where we’ll generate knight moves. Start from the point (0, 0), for which
we set sol[0][0] = 1 (the
first move of the knight). Next, iterate the positions where the chess knight can go. If there is
a position where the knight can go, then make a move there and continue the
search from this position. If it is impossible
to make a move from the current position, then make a move backward
(backtracking) and continue the search. The search ends when all numbers from 1
to n2 have been
placed on the chessboard.
The maximum size of
the chessboard is 8.
In the sol array generate the moves
of the knight.
#define MAX 9
int sol[MAX][MAX];
The arrays xMove
and yMove define the possible moves
of the knight. If the knight is in the cell (x, y), then with
one move it can go to
the cell (x + xMove[i], y + yMove[i]), where
0 ≤ i ≤ 7.
int xMove[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };
int yMove[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };
The function isSafe checks
if cell (x, y) is free.
That is, if the knight can go to cell (x, y). The answer
is affirmative if the x and y coordinates are within the chessboard
(the cells are numbered from 0 to n –
1) and the knight has not entered the cell (x, y) yet (sol[x][y] = -1).
int isSafe(int x, int y)
{
return (x >= 0 && x < n && y >= 0
&& y < n && sol[x][y] == -1);
}
The function printSolution prints a chessboard with
knight moves.
void printSolution(void)
{
for (int x = 0; x < n;
x++)
{
for (int y = 0; y < n;
y++)
printf("%2d
", sol[x][y]);
printf("\n");
}
}
The function solveKTUtil makes
a move number movei to the cell (x,
y). Continue the search with backtracking from the cell (x, y) until n2 moves are made.
int solveKTUtil(int x, int y, int movei)
{
The move number movei
is made to the cell (x, y).
sol[x][y] = movei;
If n2 moves are made, then finish the search.
if (movei == n * n) return 1;
Iterate through the
cells where you can go from (x, y). From the
cell (x, y) in one move
the knight can go to (x + xMove[i], y
+ yMove[i]), where 0 ≤ i ≤ 7.
for (int k = 0; k < 8; k++)
{
int next_x = x + xMove[k];
int next_y = y + yMove[k];
If the knight did not visit the cell (next_x, next_y) yet, then recursively run the search from it. In (next_x, next_y) the move number movei + 1 is performed.
if (isSafe(next_x, next_y))
{
if (solveKTUtil(next_x, next_y, movei + 1) == 1) return 1;
}
}
If all the moves of the knight are iterated, but it was not
possible to make a move to the free square, make a move backward
(backtracking), free the square (x, y) (sol[x][y] = -1).
sol[x][y] = -1;
return 0;
}
The function solve builds
a knight’s route using
backtracking. The function returns 0 if the route cannot be built. If there are
several solutions, the
function generates one of them.
int solve()
{
Initialize the
resulting matrix sol.
for (int x = 0; x < n;
x++)
for (int y = 0; y < n;
y++)
sol[x][y] = -1;
The chess knight starts its path from the upper left corner. The function solveKTUtil starts
path generation from cell (0, 0). The cell (0, 0) contains the number 1.
if (solveKTUtil(0,
0, 1) == 0)
{
printf("Solution
does not exist");
return 0;
}
else
printSolution();
return 1;
}
The main part of the program. Read the size of the chessboard n. Run the function solve –
solving the problem.
scanf("%d", &n);
solve();